CODE 73. Permutation Sequence

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/09/2013-10-09-CODE 73 Permutation Sequence/

访问原文「CODE 73. Permutation Sequence」

The set [1,2,3,…,n] contains a
total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

 	public String getPermutation(int n, int k) {
	// Start typing your Java solution below
	// DO NOT write main() function
	--k;
	ArrayList<Integer> numbers = new ArrayList<Integer>();
	String s = new String();
	int njiecheng = 1;
	for (int i = 1; i <= n; i++) {
		numbers.add(i);
		njiecheng *= i;
	}
	for (int j = n; j >= 1; j--) {
		int num = k / (njiecheng / j);
		s = s + numbers.get(num);
		numbers.remove(num);
		k = k % (njiecheng / j);
		njiecheng = njiecheng / j;
	}
	return s;
}